package com.atcumt.bytedance;

import java.util.Arrays;

// 快排
public class BT05 {

    // 从数组中选一个基准值，比基准值小的放在它的前面，比基准值大的放在它的后面
    // 哨兵j的使命是要找小于基准数的数，而哨兵i的使命是要找大于基准数的数，直到i和j碰头为止
    public static void quickSort(Integer[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        int i = low, j = high;
        int temp = arr[low]; // temp就是基准位

        while (i < j) {
            while (temp <= arr[j] && i < j) {
                j--; //先从右边，依次往左递减
            }
            while (temp >= arr[i] && i < j) {
                i++; //再从左边，依次往右递增
            }
            if (i < j) {
                int t = arr[j];
                arr[j] = arr[i];
                arr[i] = t; //如果满足条件则交换
            }
        }
        arr[low] = arr[i];
        arr[i] = temp; // 将基准与i和j相等位置的数字交换

        quickSort(arr, low, j - 1); //递归调用左半数组
        quickSort(arr, j + 1, high); //递归调用右半数组
    }


    public static void main(String[] args) {
        Integer[] arr = {16, 71, 2, 4, 7, 62, 13, 4, 2, 1, 8, 9, 19};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.asList(arr));
    }
}
